#include <stdio.h>
#include <stdlib.h>

typedef int KeyTpye;
typedef struct BstNode
{
    KeyTpye key;
    struct BstNode *lchild;
    struct BstNode *rchild;
}BstNode,*BiTree;
int Bst_insert(BiTree &T,KeyTpye k)
{
    BiTree TreeNew=(BiTree)calloc(1,sizeof(BstNode));
    TreeNew->key=k;
    if (NULL==T)
    {
        T=TreeNew;
        return 1;
    }
     BiTree p=T,parent;//用来查找树
     parent = p;
        while(p) {
            parent = p;
            if (k > p->key) {
                p = p->rchild;
            } else if (k < p->key) {
                p = p->lchild;
            } else {
                return 0;//相等的元素不会放入查找数
            }
        }
     //接下来是判断放入p的左边还是右边
    if (k>parent->key)//放到父亲的右边
    {
        parent->rchild=TreeNew;
    }
    else//放到父亲左边
    {
     parent->lchild=TreeNew;
    }
    return 1;
}


void Creat_Bst(BiTree &T,KeyTpye *str,int n)
{
    int i=0;
    while(i<n)
    {
        Bst_insert(T,str[i]);
        i++;
    }
}
void Mid_order(BiTree T)
{
    if (T!=NULL)
    {
        Mid_order(T->lchild);
        printf("%3d",T->key);
        Mid_order(T->rchild);
    }
}
BiTree BiSearch(BiTree T,KeyTpye k, BiTree &parent)
{
    parent = NULL;
    while(T!=NULL&&k!=T->key)
    {
        parent=T;
        if (k<T->key)
            T=T->lchild;
        else
            T=T->rchild;
    }
    return T;
}
int main() {
    BiTree T = NULL;
    KeyTpye str[]={20,30,40,50,12,24,35};
    Creat_Bst(T,str,7);
    Mid_order(T);//中序遍历二叉排序树是由小到大的
    printf("\n");
    BiTree search,parent;
    search= BiSearch(T,40,parent);
    if (search)
    {
        printf("%d\n",parent->key);
    }
    else
    {
        printf("not found");
    }
    return 0;
}
